package com.tcm.day02;

/**
 * 二分查找
 */
public class Code01_middleSearch {

    public static int middleSearch(int[] arr, int num) {
        if (null == arr || arr.length < 1) return -1;

        int L = 0;
        int R = arr.length - 1;

        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] == num) {
                return mid;
            } else if (arr[mid] < num) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return -1;
    }

    // 有序数组中找到>=num最左的位置
    public static int findMostLeftIdx(int[] arr, int num) {
        if (null == arr || arr.length == 0) return -1;

        int L = 0;
        int R = arr.length - 1;
        int ans = -1;

        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] >= num) {
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return ans;
    }

    // 有序数组中找到<=num最右的位置
    public static int findMostRightIdx(int[] arr, int num) {
        if (null == arr || arr.length == 0) return -1;

        int L = 0;
        int R = arr.length - 1;
        int ans = -1;

        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] <= num) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return ans;
    }


    public static int[] randomArray2(int len, int maxVal) {
        int arrLen = (int) (Math.random() * len) + 1;
        int[] arr = new int[arrLen];
        arr[0] = (int) (Math.random() * maxVal);

        for (int i = 1; i < arr.length; i++) {
            do {
                arr[i] = (int) (Math.random() * maxVal);
            } while (arr[i] == arr[i - 1]);
        }

        return arr;
    }

    public static void test() {
        int times = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < times; i++) {
            int[] arr = randomArray2(40, 200);
            int idx = findOneMinimum(arr);
            boolean r = check(arr, idx);
            if (!r) System.err.println("出错了");
        }
        System.out.println("测试结束");
    }

    public static boolean check(int[] arr, int idx) {
        if (arr.length == 1) return idx == 0;

        if (arr.length == 2) {
            if (arr[0] < arr[1]) return idx == 0;
            else return idx == 1;
        }
        int left = idx - 1;
        int right = idx + 1;
        boolean leftFlag = left >= 0 ? arr[left] > arr[idx] : true;
        boolean rightFlag = right < arr.length ? arr[idx] < arr[right] : true;
        return leftFlag && rightFlag;
    }

    /**
     * 数组无序，相邻的两个数不相等
     * 查询数组极小值问题
     *
     * @param arr
     * @return
     */
    public static int findOneMinimum(int[] arr) {
        if (null == arr || arr.length == 0) return -1;

        if (arr.length == 1) return 0;

        if (arr.length == 2) {
            if (arr[0] < arr[1]) {
                return 0;
            } else {
                return 1;
            }
        }

        int L = 0;
        int R = arr.length - 1;

        while (L + 1 < R) {
            int mid = (L + R) / 2;
            if (arr[mid - 1] > arr[mid] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid - 1] < arr[mid]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 13, 17, 22, 25};
        System.out.println(middleSearch(arr, 25));
        System.out.println(findMostLeftIdx(arr, 25));
        System.out.println(findMostRightIdx(arr, 8));
    }
}
